home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Language/OS - Multiplatform Resource Library
/
LANGUAGE OS.iso
/
cpp_libs
/
answrbok
/
5_2.lha
/
5_2
/
5_2b3.c
< prev
next >
Wrap
Text File
|
1993-08-08
|
1KB
|
80 lines
* Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
* The C++ Answer Book */
* Tony Hansen */
* All rights reserved. */
/ delete a word from the tree
include <tree.h>
include <string.h>
nt tree:: delnode(char *s)
tnode **parent = &head;
tnode *cur = head;
for (;;)
{
if (!cur)
return 0;
int cmp = strcmp(s, cur->tword);
// check the left subtree
if (cmp < 0)
{
parent = &cur->left;
cur = cur->left;
}
// check the right subtree
else if (cmp > 0)
{
parent = &cur->right;
cur = cur->right;
}
// equal, found it
else /* if (cmp == 0) */
{
// if more than one reference,
// just decrement the reference count
if (cur->count > 1)
cur->count--;
// if there are no children,
// delete this node and
// the reference to it
else if (!cur->left && !cur->right)
{
delete cur;
*parent = 0;
}
// if there are children, try doing
// a splice into the right node
else if (!cur->right->left)
{
*parent = cur->right;
cur->right->left = cur->left;
delete cur;
}
// find a node on the left where
// we can splice in the right node
else
{
tnode *svright = cur->right;
*parent = cur->left;
delete cur;
for (cur = *parent;
cur->right;
cur = cur->right)
;
cur->right = svright;
}
return 1;
}
}